//
//  ProblemOffer10-2.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/22.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 10- II. 青蛙跳台阶问题
 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

 示例 1：
     输入：n = 2
     输出：2
 示例 2：
     输入：n = 7
     输出：21
 示例 3：
     输入：n = 0
     输出：1
 提示：
    0 <= n <= 100
 */
@objcMembers class ProblemOffer10_2: NSObject {
    func solution() {
        print(numWaysClear(0))
        print(numWaysClear(2))
        print(numWaysClear(7))
        print(numWaysClear(12))
        print(numWaysClear(54))
        print(numWaysClear(100))
    }
    /*
     动态规划：
     因为青蛙跳台阶有2种选择，那么假如青蛙现在位于 s 级上，那么它跳到s上有2种方法:
     1> 在 s-1 级上，跳了一次
     2> 在 s-2 级上，跳了二次
     求的是总共由多少种跳法，那么到底s处，就2种跳法：从s-1跳上来 或者 从s-2跳上来
     总结：sum(s) = (sum(s-1) + 1) + (sum(s-2) + 1)
     
     1: 创建一个数组dp[n]
     2: dp[i] 表示：跳到i级，有多少种跳法
     3: dp[i] = dp[i-1] + 1 + dp[i-2] + 1
     4: 特殊台阶：
        0级台阶，不需要跳dp[0]=0;
        1级台阶，只有一种跳法dp[1]=1
     */
    func numWays(_ n: Int) -> Int {
        // 特殊台阶
        if n <= 1 {
            return 1
        }
        
        var dp:[Int] = Array(repeating: 0, count: n+1)
        dp[0] = 1
        dp[1] = 1
        for i in 2...n {
            dp[i] = dp[i-1] % 1000000007 + dp[i-2] % 1000000007
        }
        return dp[n] % 1000000007
    }
    
    /*
     动态规划：优化空间
     发现dp[i] 只与 dp[i-1] 和 dp[i]有关，所以没必要使用数组，直接创建2个变量last、lastlast
     */
    func numWaysClear(_ n: Int) -> Int {
        // 特殊台阶
        if n <= 1 {
            return 1
        }
        
        var result:Int = 0
        var lastlast = 1, last = 1
        for _ in 2...n {
            result = lastlast % 1000000007 + last % 1000000007
            lastlast = last
            last = result
        }
        return result % 1000000007
    }
    
}
